#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int g[N][N];
bool st[N];
int dis[N];
int q[N];
int n , m , s;

void dfs(int s)
{
    printf("%d ",s);
    st[s] = true;
    for(int i = 0 ; i < n ; ++i)
    {
        if(st[i] == false && g[s][i] != 0x3f3f3f3f) dfs(i);
    }
}

void bfs(int s)
{
    int hh = 0 , tt = 0;
    q[0] = s;
    st[s] = true;
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = 0 ; i < n ; ++i)
        {
            if(!st[i] && g[t][i] != 0x3f3f3f3f)
            {
                q[++tt] = i;
                st[i] = true;
            }
        }
        printf("%d ",t);
    }
}

void djikstra(int s)
{
    memset(dis,0x3f,sizeof dis);
    dis[s] = 0;
    for(int i = 0 ; i < n ; ++i)
    {
        int t = -1;
        for(int j = 0 ; j < n ; ++j) if(!st[j] && (t == -1 || dis[t] > dis[j])) t = j;
        for(int j = 0 ; j < n ; ++j) dis[j] = min(dis[j],dis[t] + g[t][j]);
        st[t] = true;
    }
}
int Prim()
{
    memset(dis,0x3f,sizeof dis);
    int res = 0;
    for(int i = 0 ; i < n ; ++i)
    {
        int t = -1;
        for(int j = 0 ; j <= n ; ++j)
            if(!st[j] && (t==-1 || dis[j] < dis[t])) t = j;
        
        if(i && dis[t] == 0x3f3f3f3f) return 0x3f3f3f3f;
        if(i) res += dis[t];
        for(int j = 0 ; j <= n ; ++j) dis[j] = min(dis[j],g[t][j]);
        st[t] = true;
    }
    return res;
}
int main()
{
    cout << "输入点数：" << endl;
    cin >> n;
    cout << "输入边数" << endl;
    cin >> m;
    cout << "输入m行数据，表示a点->b点，权值为c" << endl;
    //初始化邻接矩阵
    memset(g,0x3f,sizeof g);
    //读入边
    for(int i = 0 ; i < m ; ++i)
    {
        int a , b , c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b],c);
    }
    cout << "输入dfs起点" << endl;
    cin >> s;
    cout << "dfs结果" << endl;
    dfs(s);
    cout << endl;
    memset(st,0,sizeof st);
    cout << "输入bfs起点" << endl;
    cin >> s;
    bfs(s);
    cout << endl;
    memset(st,0,sizeof st);
    cout << "输入dijkstra起点" << endl;
    cin >> s;
    djikstra(s);
    cout << "输入目标点" << endl;
    int d;
    cin >> d;
    cout << dis[d] << endl;
    memset(st,0,sizeof st);
    cout << "最小生成树总和：" << endl;
    int n = Prim();
    if(n == 0x3f3f3f3f) cout << "不存在最小生成树" << endl;
    else cout << n << endl;
    return 0;
}